package InsertSort

func InsertSort(a []int) []int {

	for i := 1; i < len(a); i++ {
		value := a[i]
		j := i - 1
		//查找插入位置
		for ; j >= 0; j-- {
			// 从后往前找，有序部分的最后一个元素的值，比待插入元素大，则有序部分最后的1个元素右移一位
			if a[j] > value {
				a[j+1] = a[j]
			} else {
				break
			}
		}
		// 插入数据
		a[j+1] = value
	}

	return a
}

// 函数中j变量，不属于内层for的局部变量，而是属于外层for循环的局部变量，
// 所以最后a[j+1] = value，j是获取到内层循环中，j递减到多少了
